/* Set tab stop to 1 */
/*-----------------------------------------------------------------------------
 * File Name ..... parcreate.c
 *
 * Purpose ....... Contains functions for creating the parallel heap and
 *
 * Functions ..... CreateParHeap, AllocateParHeap, InsertItems, PrintParHeap
 *					  PrintLevelFlags, ExpandParHeap, PrintAllFlags, PrintFlags
 *
 * Date Written .. April 28, 1993
 *
 * Modification History
 *	 Author				Date								  Purpose
 *	 ------				----								  -------
 * Sagar Sawant		 April 28, 1993			The original version of parheap.c
 *---------------------------------------------------------------------------*/


/*-------------------------- Include Files ----------------------------------*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include "parheap.h"
#include "pardef.h"
#include <stdlib.h>


/*-------------------------- Global Variables -------------------------------*/
PARHEAP ***ParHeap;
LevelFlagType *LevelFlag;		 /* One LevelFlag per level of ParHeap */
int LastLevel1 = 0;				 /* Last level of heap excluding insert items */
int LastNode1 = 0;				  /* Last node of heap excluding insert items */
int NoOfLastItems1 = 0;			/* No. of items int last node of heap */
/* excluding insert items */
int LastLevel = 0;				  /* Last level of heap including insert items */
int LastNode = 0;					/* Last node of heap including insert items */
int NoOfLastItems = 0;			 /* No. of items int last node of heap */
/* including insert items */
int r;								  /* No. of items in one node */
PARHEAP *partmp;



/*---------------------------Extern Functions -------------------------------*/
extern void PH_GetNewSortedItems();
extern int  ParHeapCmp();

extern void PH_Merge();
extern void *MyMalloc(int);
extern void *MyCalloc(int);
extern int Get_Nth_Bit_From_Right(int,int);
extern int ceil_log2(int);
extern void PrintPHArray(FILE *, PARHEAP *, int);

/*--------------------------------- Functions -------------------------------*/
void CreateParHeap(int InitialNoOfItems);
void AllocateParHeap(int InitialNoOfLevels);
void DeAllocateParHeap(int InitialNoOfLevels);
void InsertItems(PARHEAP *NewItems,int k);
void PrintParHeap(FILE *outfile);
void PrintFlags(FILE *outfile,int LevelNo);
void PrintAllFlags(FILE *outfile);
void PrintLevelFlags(FILE *outfile,int LevelNo);
void ExpandParHeap();

/*----------------------------------------------------------------------------
 * Function ........... CreateParHeap
 *
 * Purpose ............ Calls functions to allocate memory for the parallel
 *							 heap and insert items into the heap.
 *
 * Arguments Passed ... InitialNoOfItems - No of items to be inserted initially.
 *
 * Return Value ....... None
 *
 * Globals Modified ... LastLevel1, LastNode1, NoOfLastItems1,
 *							 LastLevel, LastNode, NoOfLastItems
 *---------------------------------------------------------------------------*/
void CreateParHeap(int InitialNoOfItems)
{
    int InitialNoOfNodes, InitialNoOfLevels, i, tmp;
    PARHEAP *NewItems;

    InitialNoOfNodes = ((int) ceil((double) InitialNoOfItems / (double) r));
    InitialNoOfLevels = ceil_log2(InitialNoOfNodes) + 1;
    AllocateParHeap(InitialNoOfLevels);

    NewItems = (PARHEAP*) MyMalloc(r*sizeof(PARHEAP));
    /* All but the last one as that may have less than r items */
    for ( i=0; i < InitialNoOfNodes - 1; i++ )
    {
        PH_GetNewSortedItems(r, USE_RANDOM_DATA, MAX_ITEM_VALUE, NewItems);
        /* Insert items in heap */
        InsertItems(NewItems, r);
    }

    PH_GetNewSortedItems(r, USE_RANDOM_DATA, MAX_ITEM_VALUE, NewItems);
    /* Insert items in last node of the heap  */
    if ( (tmp = InitialNoOfItems % r) == 0)
        InsertItems(NewItems, r);
    else
        InsertItems(NewItems, tmp);

    free(NewItems);
}


/*----------------------------------------------------------------------------
 * Function ........... AllocateParHeap
 *
 * Purpose ............ Allocates memory for the parallel heap and the
 *							 level flags.
 *
 * Arguments Passed ... InitialNoOfItems - No of items to be inserted initially.
 *
 * Return Value ....... None
 *
 * Globals Modified ... ParHeap, LevelFlag
 *---------------------------------------------------------------------------*/
void AllocateParHeap(int InitialNoOfLevels)
{
    int i, j, levelbase, tmp;

    ParHeap = (PARHEAP ***)MyMalloc((InitialNoOfLevels) * sizeof (PARHEAP**) );

    LevelFlag = (LevelFlagType *) MyMalloc((InitialNoOfLevels)* sizeof(LevelFlagType) );
    memset(LevelFlag, -1, InitialNoOfLevels * sizeof(LevelFlagType) );

    /* Allocate memory for heap */
    partmp = (PARHEAP*) MyCalloc(((int)pow(2.0, InitialNoOfLevels)) * r * sizeof(PARHEAP)); 

    /*  take care of root node seperately */
    ParHeap[0] = (PARHEAP **) MyMalloc(sizeof(PARHEAP*));
    ParHeap[0][0] =  &partmp[0];

    for (i=1; i < InitialNoOfLevels; i++)
    {
        /* Find the number of nodes in this level */
        tmp = (int) ldexp(1.0, i);
        /* Find where does the node start */
        levelbase = (int) (ldexp(1.0, i) - 1) * r;

        ParHeap[i] = (PARHEAP **) MyMalloc(tmp * sizeof(PARHEAP *));
        for (j=0; j < tmp; j++)
        {
            ParHeap[i][j] = &partmp[levelbase + (j * r)];
        }
    }

#ifdef NO_CONT_MEM
    int i, j, tmp;

    ParHeap = (PARHEAP ***)MyMalloc((InitialNoOfLevels) * sizeof (PARHEAP**) );
    LevelFlag = (LevelFlagType *) MyMalloc((InitialNoOfLevels)* sizeof(LevelFlagType) );
    memset(LevelFlag, -1, InitialNoOfLevels * sizeof(LevelFlagType) );

    /*  take care of root node seperately */
    ParHeap[0] = (PARHEAP **) MyMalloc(sizeof(PARHEAP*));
    ParHeap[0][0] = (PARHEAP *) MyCalloc(r * sizeof(PARHEAP));

    for (i=1; i < InitialNoOfLevels; i++)
    {
        tmp = (int) ldexp(1.0, i);
        ParHeap[i] = (PARHEAP **) MyMalloc(tmp * sizeof(PARHEAP *));
        /*  we allocate in pairs for cache locality during update operations */
        for (j=0; j < tmp; j += 2)
        {
            partmp = (PARHEAP *) MyCalloc(2 * r * sizeof(PARHEAP));
            ParHeap[i][j] = partmp;
            ParHeap[i][j + 1] = &partmp[r];
        }
    }
#endif
}


/*----------------------------------------------------------------------------
 * Function ........... InsertItems
 *
 * Purpose ............ Inserts k items into the heap. This function is used
 *							 only during creation of heap.
 *
 * Arguments Passed ... NewItems - Pointer to array containing new items.
 *							 k - Number of new items
 *
 * Return Value ....... None
 *
 * Globals Modified ... ParHeap, LevelFlag
 *---------------------------------------------------------------------------*/
void InsertItems(PARHEAP *NewItems, int k)
{
    int CurrentLevel = 0, CurrentNode = 0, n;
    PARHEAP *Temp, *memtemp;
    Temp = (PARHEAP *)MyMalloc(2*r * sizeof(PARHEAP));
    memtemp = (PARHEAP *)MyMalloc(2*r * sizeof(PARHEAP));

    /* if last node full, proceed to next node */
    if (NoOfLastItems1 == r)
    {
        /* If Lastlevel is full add a level */
        if (LastNode1 == (int) (ldexp(1, LastLevel1)-1) )
        {
            LastLevel1++;
            /* The target node will be the first node in this new level */
            LastNode1 = 0;
        }
        else
        {
            /* If the last node is not full add the node there */
            LastNode1++;
        }
        NoOfLastItems1 = 0;
    }
    while (CurrentLevel < LastLevel1)
    {
        //PH_Merge(ParHeap[CurrentLevel][CurrentNode], r, NewItems, k, Temp);
        PH_Merge(&partmp[HEAPINDEX(CurrentLevel,CurrentNode,0,r)], r, NewItems, k, Temp);
        //memcpy(ParHeap[CurrentLevel][CurrentNode], Temp, r*sizeof(PARHEAP));
        memcpy(&partmp[HEAPINDEX(CurrentLevel,CurrentNode,0,r)], Temp, r*sizeof(PARHEAP));
        memcpy(NewItems, &Temp[r], k*sizeof(PARHEAP));
        n = LastLevel1 - CurrentLevel;
        if ( (Get_Nth_Bit_From_Right(LastNode1, n) == 0) )
            CurrentNode = 2 * CurrentNode;
        else
            CurrentNode = (2 * CurrentNode) + 1;
        CurrentLevel++;
    }
    //PH_Merge(ParHeap[LastLevel1][LastNode1], NoOfLastItems1,NewItems,k, memtemp);
    PH_Merge(&partmp[HEAPINDEX(LastLevel1,LastNode1,0,r)], NoOfLastItems1,NewItems,k, memtemp);
    //memcpy(ParHeap[LastLevel1][LastNode1], memtemp, (NoOfLastItems1+k)*sizeof(PARHEAP));
    memcpy(&partmp[HEAPINDEX(LastLevel1,LastNode1,0,r)], memtemp, (NoOfLastItems1+k)*sizeof(PARHEAP));
    NoOfLastItems1 = NoOfLastItems1 + k;

    LastLevel = LastLevel1;
    LastNode = LastNode1;
    NoOfLastItems = NoOfLastItems1;
    free(Temp);
    free(memtemp);
}


/*----------------------------------------------------------------------------
 * Function ........... PrintParHeap
 *
 * Purpose ............ Prints the parallel heap
 *
 * Arguments Passed ... outfile - the print file.
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void PrintParHeap(outfile)
FILE *outfile;
{
    int i, j, tmp;

    fprintf(outfile, "\nPARALLEL HEAP\n");
    fprintf(outfile, "~~~~~~~~ ~~~~\n");
    fprintf(outfile, "LastLevel1 = %d, LastNode1 = %d, NoOfLastItems1 = %d\n", LastLevel1, LastNode1, NoOfLastItems1);
    fprintf(outfile, "LastLevel = %d, LastNode = %d, NoOfLastItems = %d\n\n", LastLevel, LastNode, NoOfLastItems);
    if ( (LastLevel > 0) || (LastNode > 0) || (NoOfLastItems > 0) )
    {
        for ( i=0 ; i <= LastLevel ; i++ )
        {
            fprintf(outfile, "Level %d\n", i);
            tmp = (int) ldexp(1.0, i);
            for ( j=0 ; j<tmp ; j++)
            {
                if ((i == LastLevel) && (j > LastNode))
                    break;
                fprintf(outfile, "      Node %d = ", j);
                /*             PrintIntArray(outfile, &(ParHeap[i][j][0].item), r); */
                PrintPHArray(outfile, ParHeap[i][j], r);
                fprintf(outfile, "\n");
            }
            PrintFlags(outfile, i);
        }
    }
    else
        fprintf(outfile, "No elements inside parallel heap\n");
    fprintf(outfile, "------------------------------------------------------\n");

}


/*----------------------------------------------------------------------------
 * Function ........... PrintFlags

 * Purpose ............ Prints the level flags for the specified level of the
 *							 parallel heap. The function is called by PrintParHeap
 *							 to print the flags alongside the parallel heap.
 *
 * Arguments Passed ... outfile - the print file.
 *							 LevelNo - level whose flags are to be printed
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void PrintFlags(outfile, LevelNo)
FILE *outfile;
int LevelNo;
{
    int i;
    if (LevelFlag[LevelNo].delete_flag != -1)
        fprintf(outfile, "		Delete Flag = %d\n", LevelFlag[LevelNo].delete_flag);
    /* &&& Begin */
    for ( i=0 ; i < MAX_INSERTS ; i++ )
    {
        if (LevelFlag[LevelNo].Inserts[i].insert_flag != -1)
            fprintf(outfile,
                    "  Insert %d : Flag = %d, Level = %d, Offset = %d, No of items = %d\n",
                    i,
                    LevelFlag[LevelNo].Inserts[i].insert_flag,
                    LevelFlag[LevelNo].Inserts[i].insert_level,
                    LevelFlag[LevelNo].Inserts[i].insert_offset,
                    LevelFlag[LevelNo].Inserts[i].insert_no_of_items);
    }
    /* &&& End **/
}


/*----------------------------------------------------------------------------
 * Function ........... PrintAllFlags
 *
 * Purpose ............ Prints all the level flags of the parallel heap.
 *
 * Arguments Passed ... outfile - the print file.
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void PrintAllFlags(outfile)
FILE *outfile;
{
    int i;

    fprintf(outfile, "-------------- LEVEL FLAGS --------------\n");
    for ( i=0 ; i<=LastLevel1 ; i++ )
        PrintLevelFlags(outfile, i);
    fprintf(outfile, "-------------- LEVEL FLAGS OVER--------------\n");
}


/*----------------------------------------------------------------------------
 * Function ........... PrintLevelFlags
 *
 * Purpose ............ Prints the level flags of the specified heap. This
 *							 function is called by PrintAllFlags while printing
 *							 all the level flags of the parallel heap.
 *
 * Arguments Passed ... outfile - the print file.
 *							 LevelNo - the level whose flags are to be printed
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void PrintLevelFlags(outfile, LevelNo)
FILE *outfile;
int LevelNo;
{
    int i;  /* &&& */

    fprintf(outfile, "LEVEL FLAGS AT LEVEL %d\n", LevelNo);
    fprintf(outfile, "Delete Flag = %d\n", LevelFlag[LevelNo].delete_flag);
    /* &&& Begin
    	fprintf(outfile,
      "Insert 1 : Flag = %d, Level = %d, Offset = %d, No of items = %d\n",
      LevelFlag[LevelNo].insert_flag1,
      LevelFlag[LevelNo].insert_level1,
      LevelFlag[LevelNo].insert_offset1,
      LevelFlag[LevelNo].insert_no_of_items1);
    	fprintf(outfile,
      "Insert 2 : Flag = %d, Level = %d, Offset = %d, No of items = %d\n",
      LevelFlag[LevelNo].insert_flag2,
      LevelFlag[LevelNo].insert_level2,
      LevelFlag[LevelNo].insert_offset2,
      LevelFlag[LevelNo].insert_no_of_items2);
     &&& End **/
    /* &&& Begin */
    for ( i=0 ; i < MAX_INSERTS ; i++ )
        if (LevelFlag[LevelNo].Inserts[i].insert_flag != -1)
            fprintf(outfile,
                    "  Insert %d : Flag = %d, Level = %d, Offset = %d, No of items = %d\n",
                    i,
                    LevelFlag[LevelNo].Inserts[i].insert_flag,
                    LevelFlag[LevelNo].Inserts[i].insert_level,
                    LevelFlag[LevelNo].Inserts[i].insert_offset,
                    LevelFlag[LevelNo].Inserts[i].insert_no_of_items);
    /* &&& End **/
}


/*----------------------------------------------------------------------------
 * Function ........... ExpandParHeap
 *
 * Purpose ............ Allocates memory for one more level of the parallel
 *							 heap.
 *
 * Arguments Passed ... None
 *
 * Return Value ....... None
 *
 * Globals Modified ... ParHeap, LevelFlag, LastLevel
 *---------------------------------------------------------------------------*/
void ExpandParHeap()
{
    int j, tmp;

    LastLevel++;
    tmp = (int) ldexp(1.0, LastLevel);
    ParHeap[LastLevel] = (PARHEAP **) MyMalloc(tmp * sizeof(PARHEAP *));
    for ( j=0 ; j<tmp ; j++)
        ParHeap[LastLevel][j] = (PARHEAP *) MyCalloc(r * sizeof(PARHEAP));
    LastNode = 0;
    memset(&LevelFlag[LastLevel], -1, sizeof(LevelFlagType) );
}





